caboCity.implement({
	iniVarRoad: function(){
		var n = this.grid.gridNum.x * this.grid.gridNum.y;
		this.roadhash = new Array(n); //Know if a position has a single road.
		this.road = new Array(n); //Stores all single roads.
		this.r = {};
		this.r.empire;
	}
	
	,createEmpirePath: function(){
		var offset = {x: this.grid.gridNum.x/4 , y: this.grid.gridNum.y/4};
		var startcoor = {x: Math.floor(Math.random()*(this.grid.gridNum.x-offset.x*2)+offset.x ), y:0};
		var middlecoor = {
			x: Math.floor( Math.random()*(this.grid.gridNum.x-offset.x*2)+offset.x ),
			y: Math.floor( Math.random()*(this.grid.gridNum.y-offset.y*2)+offset.y )
		}
		var endcoor = {x: middlecoor.x ,y:this.grid.gridNum.y-1};
		this.r.empire = {start: startcoor , end: endcoor};
		
		this.newPath(startcoor, middlecoor);
		this.newPath(middlecoor, endcoor);
		
		this.road[this.coor2vec(startcoor)].empire = true; //Set it's from empire path
		this.road[this.coor2vec(endcoor)].empire = true; //Set it's from empire path
		
		this.checkAllRoadConnectedEmpire();
	}
	
	//Be carefull
	,setRoad: function(coor, r){
		this.takeThisTile(coor, d.tt.road);
		var m = this.coor2vec(coor);
		this.road[ m ] = r;
		this.roadhash[ m ] = true;
	}
	//Be carefull
	,unsetRoad: function(coor){
		this.freeThisTile(coor);
		var m = this.coor2vec(coor);
		this.roadhash[m] = null;
		this.road[ m ] = null;
	}
	
	//NORMAL PATH
	//Add a new auto-path
	,newPath: function(inicoor, endcoor){
		$$('.shadow').destroy(); //Destroy all previus shadow elements
		if(!this.isTileBuildable(inicoor) || !this.isTileBuildable(endcoor)){
			if((!this.isTileBuildable(inicoor) && !this.isRoad(inicoor)) || (!this.isTileBuildable(endcoor) && !this.isRoad(endcoor)) )
				return; //The path isn't posible.
		}
		//Convert to pathlist (auto path)
		var pathList = this.convertToPathList(inicoor, endcoor);
		pathList.each(function(road){
			this.newRoad(road)
		}, this);
		
		//TODO: check new roads are connected to empire
		this.checkAllRoadConnectedEmpire();
	}
	
	//SHADOW PATH
	//Add a new shadow auto-path
	,newPathShadow: function(inicoor, endcoor){
		$$('.shadow').destroy(); //Destroy all previus shadow elements
		if(!this.isTileBuildable(inicoor) || !this.isTileBuildable(endcoor)){
			if((!this.isTileBuildable(inicoor) && !this.isRoad(inicoor)) || (!this.isTileBuildable(endcoor) && !this.isRoad(endcoor)) )
				return; //The path isn't posible.
		}
		//Convert to pathlist (auto path)
		var pathList = this.convertToPathList(inicoor, endcoor);
		pathList.each(function(road){
			this.newRoadShadow(road);
		}, this);
	}
	
	//Add a road
	,newRoad: function(coor){
		if(!this.isTileBuildable(coor)) return false;
		
		var r = new cRoad(coor);
		this.setRoad(coor, r);
		
		var pos = this.p(coor);
		var el = new Element('div', {
			styles: {
				left: pos.x,
				top: pos.y
			}
		});
		el.addClass('isopers').addClass('road').addClass(d.e.c.road.normal);
		
		el.inject(this.cont);
		
		r.el = el;
		return true;
	}
	
	//Add single road shadow
	,newRoadShadow: function(coor){
		if(!this.isTileBuildable(coor)) return false;
		var pos = this.p(coor);
		var el = new Element('div', {
			styles: {
				left: pos.x,
				top: pos.y
			}
		});
		el.addClass('shadow').addClass('isopers').addClass('road').addClass(d.e.c.road.shadow);
		
		el.inject(this.cont);
		return true;
	}
	
	//Check if a coor is a road
	,isRoad: function(coor){
		var is = this.roadhash[ this.coor2vec(coor) ];
		return is;
	}
	//From and element with size
	,isRoadNearFromElement: function(from, size, empire){
		var isNear = false;
		var toX = from.x+size.x+2;
		var toY = from.y+size.y+2;
		for(var i=from.x-2; i<toX && !isNear; ++i){
			for(var j=from.y-2; j<toY && !isNear; ++j){
				if(i!=from.x || j!=from.y) {
					if(this.isRoad({x:i, y:j})) isNear = true;
					if(empire && isNear && !this.road[ this.coor2vec({x:i, y:j}) ].empire ) isNear = false;
				}
			}
		}
		return isNear;
	}
	//From a single tile
	,isRoadNearFrom: function(from, empire){
		return isRoadNearFromElement(from, {x:1, y:1}, empire);
	}
	
	//Return null if no related road have been found.
	//Return an array with near roads.
	,getRoadsNearElement: function(from, size, empire){
		var roads = new Array();
	
		var isNear = false;
		var toX = from.x+size.x+2;
		var toY = from.y+size.y+2;
		for(var i=from.x-2; i<toX; ++i){
			for(var j=from.y-2; j<toY; ++j){
				if(i!=from.x || j!=from.y) {
					var rc = {x:i, y:j};
					if(this.isRoad(rc)) isNear = true; //Está cerca de una carretera
					else isNear = false;
					if(empire && isNear && !this.road[ this.coor2vec(rc) ].empire) isNear = false; //Está cerca de una carretera y es del imperio.
					if(isNear){
						var isIn = false;
						roads.each(function(r){ //Check if road in pre-selected
							if(r.x == rc.x && r.y == rc.y) {
								isIn = true;
								return;
							};
						});
						if(!isIn) roads.include(rc); //Add the road to the list.
					}
				}
			}
		}
		
		if(roads.length > 0) return roads;
		else return null;
	}
	,isRoadTransitable: function(from, to){
		if(this.roadhash[this.coor2vec(to)] == true) return true;
		else return false;
	}
	/*//********* rethink
	, CHANGEisRoadIntersection: function(from, dir){
		var nroad = 0;
		
		if(dir != 1 && isRoadTransitable(from, {x:from.x, y:from.y-1})) nroad++;
		if(dir != 2 && isRoadTransitable(from, {x:from.x-1, y:from.y})) nroad++;
		if(dir != 3 && isRoadTransitable(from, {x:from.x+1, y:from.y})) nroad++;
		if(dir != 4 && isRoadTransitable(from, {x:from.x, y:from.y+1})) nroad++;
		
		return nroad;
	}*/
	,removeRoad: function(coor){
		var p = this.coor2vec(coor);
		var r = this.road[ p ];
		if(!r || !r.remove()) return false; //It can't be deleted
		this.unsetRoad(coor);
		
		this.checkAllRoadConnectedEmpire();
		
		return true;
	}
	
	//Check if ALL actual roads are connected to the empire path.
	//BFS algorithm. Based: http://en.wikipedia.org/wiki/Breadth-first_search
	,checkAllRoadConnectedEmpire: function(){
		var coor = this.r.empire.start;
		var n = this.grid.gridNum.x*this.grid.gridNum.y; //The array size
		var src = this.coor2vec(coor);
		
		var q = new Array();
		var setq = new Array(n);
		
		q.include(src);
		setq[src] = true;
		
		while(q.length != 0){
			var v = q.shift();
			
			/*Related edges from v START*/
			var edges = new Array(); //Contains edges from v
			var c = {};
			c.y = Math.floor(v/this.grid.gridNum.x);
			c.x = v - c.y*this.grid.gridNum.x;
			var next = {x: c.x, y:c.y-1}; //Top
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			next = {x:c.x-1, y:c.y};//Left
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			next = {x:c.x+1, y:c.y}; //Right
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			next = {x:c.x, y:c.y+1}; //Bottom
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			/*Related edges from v END*/
			
			edges.each(function(w){
				if(!setq[w]){
					setq[w] = true;
					q.include(w);
				}
			});
		}
		
		//Detect if each road is connected.
		this.road.each(function(r){
			if(r){ //A bug? (Required for when you delete a road.
				if(setq[ r.vec ] == true) {
					r.connectedEmpire();
				} else {
					r.noConnectedEmpire();
				}
			}
		}.bind(this));
		
	}
	, Dijkstra: function(startcoor, endcoor){
		/*Auxiliar vars*/
		var v;
		var n = this.grid.gridNum.x*this.grid.gridNum.y; //The array size
		
		var src = this.coor2vec(startcoor); //Source
		var dest = this.coor2vec(endcoor); //Dest
		
		var dist = new Array(n);
		var prev = new Array(n);
		var seter = new Array(n);
		for(var u=0; u<n; ++u){
			dist[u] = Infinity;
			prev[u] = src;
			seter[u] = false;
		}
		dist[src] = 0;
		while(!seter[dest]){
			var minor = Infinity;
			for(var u=0; u<n; ++u){
				if(!seter[u] && dist[u] < minor){
					minor = dist[u]; v = u;
				}
			}
			seter[v] = true;
			
			/*Related edges START*/
			var edges = new Array(); //Contains edges from v
			var c = {};
			c.y = Math.floor(v/this.grid.gridNum.x);
			c.x = v - c.y*this.grid.gridNum.x;
			var next = {x: c.x, y:c.y-1}; //Top
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			next = {x:c.x-1, y:c.y};//Left
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			next = {x:c.x+1, y:c.y}; //Right
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			next = {x:c.x, y:c.y+1}; //Bottom
			if(this.isRoadTransitable(c, next)) edges.include(this.coor2vec(next));
			/*Related edges END*/

			edges.each(function(w){
				if(!seter[w] && dist[w] > dist[v]+1 ){
					dist[w] = dist[v]+1;
					prev[w] = v;
				}
			});
		}
		
		var now = dest;
		var pathlist = new Array(); //At last position it contains the initial coor
		while(now != src){
			pathlist.push( this.vec2coor(now) );
			now = prev[now];
		}
		pathlist.push( this.vec2coor(now) ); //src position.
		
		return pathlist;
	}
});

var cRoad = new Class({
	'initialize': function(coor){
		this.coor = coor;
		this.vec = newCaboCity.coor2vec(coor);
		this.el = null;
		
		this.empire = false;
		this.noEmpireID = null;
	}
	, remove: function(){
		var start = newCaboCity.r.empire.start;
		var end = newCaboCity.r.empire.end;
		if((start.x==this.coor.x && start.y==this.coor.y) || (end.x==this.coor.x && end.y==this.coor.y)) return false;//It can't be deleted
		this.el.destroy();
		
		return true;
	}
	
	//Trigger when it is detected that the road is connected to the empire
	, connectedEmpire: function(){
		this.empire = true;
	}
	
	//Trigger when it is detected that the road ISN'T connected to the empire
	, noConnectedEmpire: function(){
		this.empire = false;
	}
});
